package pers.qianyu.month_202012.date_20201203;

/**
 * [Leetcode 每日一题]
 * 204. 计数质数
 * https://leetcode-cn.com/problems/count-primes/
 *
 * @author mizzle rain
 * @date 2020-12-03 14:43
 */
public class CountPrimes {
    /**
     * 枚举法：超时
     */
    public int countPrimes(int n) {
        int res = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime(i)) {
                res++;
            }
        }
        return res;
    }

    private boolean isPrime(int target) {
        double sqrt = Math.sqrt(target);
        for (int i = 2; i <= sqrt; i++) {
            if (target % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int result = new CountPrimes().countPrimes(10);
        System.out.println("result = " + result);
    }
}
